Fast Alloc and Free

TAD 2003

Introduction

This describes a very quick, easy (and old) method for allocating and freeing lots of small data structures. If you're writing a program that needs to deal with data structures then read on...

Years ago...

I was writing a simple shoot-em-up game back on the Atari ST which needed to keep track of lots of different software sprites. It needed to allocate a small sprite structure for the dozens of different size bullets and missiles. As you can imagine drawing everything using a 8 Mhz CPU was tricky, trying to keep the frame rate under the magic 20ms, so every routine needed to be minimal, so no fancy virtual-disk code, just blindingly fast alloc and free.

So what's the best way to handle almost randomly used data structures? The structures I needed to manage all had a fixed, constant size. This could help speed up things by a few clock cycles, although the method I'll describe in a short while doesn't use this fact. To keep things down to an absolute minimum we can reserve a block of memory and split it up into N data structures. Now we've got our block of N data structures we still need a method to manage them, mark which ones are free and which are used.

The Flag-loop method

This is probably the easiest method (and one of the slowest). We store a bit flag in each data structure that indicates whether it is free or used. The code to allocate a structure looks like this:

alloc:
        lea esi, STRUCT_BUFFER
        Mov ecx, MAX_NUMOF_DATA_STRUCTS
look:
        bt [esi+theflag], ACTIVE_F
        jz found
        add esi, SIZEOF_DATA_STRUCT
        dec ecx
        jnz look
       ... no more structures left !! ...
found:
        bts [esi+flags], ACTIVE_F
        ... [DS:ESI] ---> data structure

A similar loop could be used to deal with the active data structures. Checking the ACTIVE_F flag and then only processing those structures.

The problem with the above code is that it steps through each data structure. In the worst case it will repeat MAX_NUMOF_DATA_STRUCTS-1 before finding a free structure.

Pop goes the weasel.

Okay, what about a method that is even quicker than a linked-list? Remember that we need a method that handles 'randomly' allocated and freed structures so we can't use a pointer to alloc the next data structure from our buffer and increase it by SIZEOF_DATA_STRUCT :(

In fact we will use a pointer, but use an different structure, in fact a stack!

Because we know the maximum number of structures we have, we can use an array of MAX_NUMOF_DATA_STRUCTS pointers to record which ones are free. At init time we set the array of pointers like this:

 .DATA?
struct_stack dd MAX_NUMOF_DATA_STRUCTS dup (?)
 .CODE
       lea esi, STRUCT_BUFFER
       lea edi, STRUCT_STACK
       mov ecx, MAX_NUMOF_DATA_STRUCTS
init:
       mov [edi], esi
       add edi, 4
       add esi, SIZEOF_DATA_STRUCT
       dec ecx
       jnz init
       mov [struct_sp], edi

The FAST alloc

Now all we need is a stack pointer (or an index) so we can alloc from our STRUCT_BUFFER quickly. We can use the same stack pointer to free structures too.

 .DATA?
   struct_sp dd ?

The allocation could not be simpler :)

Fast_alloc:
       sub [struct_sp], 4
       mov eax, [struct_sp]
       mov eax, [eax]

And likewise the free routine is just as easy.

Fast_free: 
       mov edx, [struct_sp]
       mov [edx], eax 
       add [struct_sp], 4

Short and Sweet

Basically all we are doing is using a stack to store a list of data structure addresses on. Don't you agree this is much faster than a linked-list? Thanks to BeerHunter for describing this idea to me all those years ago (cheerz mate).

Happy stacking.

TAD